package pers.qianyu.month_202101.date_20210120;

import pers.qianyu.util.model.*;

/**
 * 124. 二叉树中的最大路径和
 * https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/
 *
 * @author mizzle rain
 * @date 2021-01-20 16:11
 */
public class MaxPathSum {
    private int res;

    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        res = root.val;
        recur(root);
        return res;
    }

    // 返回从当前结点往下走的最大值
    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(recur(root.left), 0);
        int right = Math.max(recur(root.right), 0);
        res = Math.max(left + right + root.val, res);
        return Math.max(left, right) + root.val;
    }
}
